/*
 * @Author: Starfish_DL
 * @Date: 2020-11-21 23:18:34
 * @LastEditors: Starfish_DL
 * @LastEditTime: 2020-11-22 19:40:30
 * @CurrentVersion: 1.0
 * @Description:
 */

#include "AdjGraph.h"
#include "LinkQueueBox.h"
#include<iostream>
using namespace std;

int visited[MAXVER_MATGRAPH][MAXVER_MATGRAPH];
void InitVisited();

ArcNode::ArcNode(Box a)
{
    this->adjvex = a;
    this->weight = 0;
    this->nextarc = nullptr;
}

ArcNode::ArcNode(Box a, int weight)
{
    this->adjvex = a;
    this->weight = weight;
    this->nextarc = nullptr;
}

ArcNode::ArcNode(Box a, ArcNode* next)
{
    this->adjvex = a;
    this->weight = 0;
    this->nextarc = next;
}

ArcNode::ArcNode(Box a, int weight, ArcNode* next)
{
    this->adjvex = a;
    this->weight = weight;
    this->nextarc = next;
}

ArcNode::~ArcNode()
{
}

VNode::VNode()
{
    this->data = Box(0,0);
    this->first = nullptr;
}

VNode::VNode(Box data)
{
    this->data = data;
    this->first = nullptr;
}

VNode::VNode(Box data, ArcNode* f)
{
    this->data = data;
    this->first = f;
}

VNode::~VNode()
{
}

AdjGraph::AdjGraph(MatGraph *m)
{
    this->e = 0;
    VNode p;
    ArcNode* s;
    for (int i = 0; i < m->n; i++)
    {
        p = VNode(Box(i/MAXVER_MATGRAPH,i%MAXVER_MATGRAPH));
        this->adjlist[i] = p;
        for (int j = m->n - 1; j >= 0; j--)
        {
            if (m->edges[i][j] == 1)
            {
                s = new ArcNode(Box(j / MAXVER_MATGRAPH, j % MAXVER_MATGRAPH), this->adjlist[i].first);
                this->adjlist[i].first = s;
                this->e++;
            }
        }
    }
    this->n = m->n;
    cout << "A Graph has been created!" << endl;
    cout << "n:" << this->n << endl;
    cout << "e:" << this->e << endl;
}

AdjGraph::~AdjGraph()
{
    ArcNode* p, * pre;
    for (int i = 0; i < this->n; i++)
    {
        p = this->adjlist[i].first;
        if (p!= nullptr)
        {
            pre = p->nextarc;
            while (pre != nullptr)
            {
                delete p;
                p = pre;
                pre = pre->nextarc;
            }
            delete p;
        }
    }
}

void AdjGraph::DispGraph()
{
    for (int i = 0; i < this->n; i++)
    {
        cout << "Vertex";
        this->adjlist[i].data.DisBox();
        cout << ":";
        ArcNode* p = this->adjlist[i].first;
        while (p != nullptr)
        {
            cout << " ";
            p->adjvex.DisBox();
            cout << "," << p->weight;
            p = p->nextarc;
        }
        cout << endl;
    }
}

void AdjGraph::DFS(Box v)
{
    visited[v.x][v.y] = 1;
    cout << "Vertex";
    v.DisBox();
    cout << endl;
    ArcNode* s = this->adjlist[v.x*MAXVER_MATGRAPH+v.y].first;
    while (s != nullptr)
    {
        if (visited[s->adjvex.x][s->adjvex.y] != 1)
        {
            this->DFS(s->adjvex);
        }
        s = s->nextarc;
    }
}

void AdjGraph::BFS(Box v)
{
    InitVisited();
    ArcNode* s;
    BoxLinkQueue queue = BoxLinkQueue(v);
    cout << "Vertex";
    v.DisBox();
    cout << endl;
    visited[v.x][v.y] = 1;
    while (!queue.IsEmpty())
    {
        Box temp = queue.OutQueue();
        s = this->adjlist[temp.x * MAXVER_MATGRAPH + temp.y].first;
        while (s != nullptr)
        {
            if (visited[s->adjvex.x][s->adjvex.y] != 1)
            {
                queue.EnQueue(s->adjvex);
                cout << "Vertex";
                s->adjvex.DisBox();
                cout << endl;
                visited[s->adjvex.x][s->adjvex.y] = 1;
            }
            s = s->nextarc;
        }
    }
}

void AdjGraph::DFSMapRecursion(Box start, Box end, Box *path,int step)
{
    visited[start.x][start.y] = 1;
    step++;
    path[step] = start;
    if (start.x==end.x && start.y==end.y)
    {
        for (int i = 0; i < step; i++)
        {
            path[i].DisBox();
            cout << endl;
        }
        cout << step;
        delete[] path;
        return;
    }
    else
    {
        ArcNode* s = this->adjlist[start.x * MAXVER_MATGRAPH + start.y].first;
        while (s!=nullptr)
        {
            if (visited[s->adjvex.x][s->adjvex.y]!=1)
            {
                this->DFSMapRecursion(s->adjvex, end,path,step);
            }
            s = s->nextarc;
        }
    }
}

void AdjGraph::BFSMap(Box start, Box end)
{
    InitVisited();
    Box* pathTrace = new Box[MAXVER_MATGRAPH * MAXVER_MATGRAPH];
    ArcNode* s;
    BoxSQueue queue = BoxSQueue(start);
    visited[start.x][start.y] = 1;
    pathTrace[queue.down] = Box(queue.head, queue.down);
    while (!queue.IsEmpty())
    {
        Box temp = queue.OutSQ();
        s = this->adjlist[temp.x * MAXVER_MATGRAPH + temp.y].first;
        while (s!=nullptr)
        {
            if (visited[s->adjvex.x][s->adjvex.y]!=1)
            {
                queue.EnSQ(s->adjvex);
                visited[s->adjvex.x][s->adjvex.y] = 1;
                pathTrace[queue.down] = Box(queue.head, queue.down);
                if (s->adjvex.x==end.x && s->adjvex.y==end.y)
                {
                    cout << "The shortest path has found." << endl;
                    int i = queue.down;
                    while (i>=0)
                    {
                        queue.data[i].DisBox();
                        cout << endl;
                        i = pathTrace[i].x;
                    }
                    delete[] pathTrace;
                    return;
                }
            }
            s = s->nextarc;
        }
    }
    cout << "The shortest path has NO found!" << endl;
    delete[] pathTrace;
    return;
}

void InitVisited()
{
    for (int i = 0; i < MAXVER_MATGRAPH; i++)
    {
        for (int j = 0; j < MAXVER_MATGRAPH; j++)
        {
            visited[i][j] = 0;
        }
    }
}
